import collections


class Tree:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.flag = 0


class AutocompleteSystem(object):

    def __init__(self, sentences, times):
        """
        :type sentences: List[str]
        :type times: List[int]
        """
        self.root = Tree('*')
        self.last_node = None
        self.already_input = collections.deque()
        for i, sentence in enumerate(sentences):
            node = self.root
            for j in range(len(sentence)):
                if sentence[j] in node.neighbors:
                    node = node.neighbors[sentence[j]]
                else:
                    tree = Tree(sentence[j])
                    node.neighbors[sentence[j]] = tree
                    node = tree
            node.flag += times[i]

    def search(self, node, s):
        if node.flag:
            self.out.append((-node.flag, s))
        for key in node.neighbors:
            self.search(node.neighbors[key], s + key)



    def input(self, c):
        """
        :type c: str
        :rtype: List[str]
        """
        if c != '#':
            self.already_input.append(c)
            if not self.last_node:
                self.last_node = self.root
            if c in self.last_node.neighbors:
                self.last_node = self.last_node.neighbors[c]
                s = ''.join(self.already_input)
                self.out = []
                self.search(self.last_node, s)
                self.out.sort()
                return_out = []
                for i in range(min(3, len(self.out))):
                    return_out.append(self.out[i][1])
                return return_out
            else:
                tree = Tree(c)
                self.last_node.neighbors[c] = tree
                self.last_node = tree
                return []
        else:
            self.last_node.flag += 1
            self.already_input = collections.deque()
            self.last_node = None
            return []


sentences = ["i love you", "island", "iroman", "i love leetcode"]
times = [5, 3, 2, 2]
obj = AutocompleteSystem(sentences, times)
print(obj.input('i'))
print(obj.input(' '))
print(obj.input('a'))
print(obj.input('#'))
print(obj.input('i'))
print(obj.input(' '))
print(obj.input('a'))
print(obj.input('#'))
print(obj.input('i'))
print(obj.input(' '))
print(obj.input('a'))
print(obj.input('#'))
